//
// Created by 紫霄 on 2020/5/10.
//

#ifndef LEETCODE_31_H
#define LEETCODE_31_H
#include <stack>
#include <vector>
using namespace std;
class Solution {
public:
  bool validateStackSequences(vector<int> &pushed, vector<int> &popped) {
    stack<int> temp;
    auto curPushed = pushed.begin();
    auto pushEnd = pushed.end();
    for (int i = 0; i < popped.size();) { // 对于popped内元素的各数；
      if (curPushed != pushEnd && *curPushed == popped[i]) {
        // 假如pushed当前的元素就是popped[i]，直接弹过去；
        ++curPushed;
        ++i;
      } else if (!temp.empty() && temp.top() == popped[i]) {
        // 假如暂存栈的栈顶元素为popped[i]
        ++i;
        temp.pop();
      } else {
        if (curPushed != pushEnd) { // pushed 还有元素，推入暂存栈，进入循环；
          temp.push(*curPushed);
          ++curPushed;
        } else {
          return false;
        }
      }
    }
    return true;
  }
};
#endif // LEETCODE_31_H
